package com.yangzhe.algorithm.c015;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/min-stack/
 */
public class GetMinStack {
    /**
     * 这里用的Java内置的栈，每个方法常数时间不优秀
     */
    class MinStack1 {
        /**
         * 数据栈
         */
        public Stack<Integer> stack;
        /**
         * 数据栈最小值栈，栈顶存储数据栈中最小值
         */
        public Stack<Integer> minStack;

        public MinStack1() {
            stack = new Stack<>();
            minStack = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);

            if (minStack.isEmpty() || minStack.peek() > val) {
                // 为空或栈顶比新来的值要大，则压入新来的值，当前栈最小值变化
                minStack.push(val);
            } else {
                // 如果栈顶比新来的值小，则直接压入以前的栈顶
                minStack.push(minStack.peek());
            }
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        /**
         * 获取堆栈中的最小元素。
         *
         * @return
         */
        public int getMin() {
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        MinStack2 minStack2 = new MinStack2();
        minStack2.push(-2);
        minStack2.push(0);
        minStack2.push(-3);
        minStack2.getMin();
        minStack2.pop();
        minStack2.top();
        minStack2.getMin();
    }

    /**
     * 可以用数组实现栈，常数时间优秀，但是栈不可扩展，需要不停尝试leetcode的极限，此时8001是极限
     */
    static class MinStack2 {
        private static final int MAX_LENGTH = 8001;
        public int[] data;
        public int[] min;
        /**
         * 栈顶 + 1的位置
         */
        private int stackTop = 0;

        public MinStack2() {
            data = new int[MAX_LENGTH];
            min = new int[MAX_LENGTH];
        }

        public void push(int val) {
            data[stackTop] = val;
            if (stackTop == 0 || min[stackTop - 1] > val) {
                min[stackTop] = val;
            } else {
                min[stackTop] = min[stackTop - 1];
            }
            stackTop++;
        }

        public void pop() {
            stackTop--;
        }

        public int top() {
            return data[stackTop - 1];
        }

        public int getMin() {
            return min[stackTop - 1];
        }
    }

}
